//输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。 
//
// 
//
// 示例 1： 
//
// 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
//输出：[1,2,3,6,9,8,7,4,5]
// 
//
// 示例 2： 
//
// 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
//输出：[1,2,3,4,8,12,11,10,9,5,6,7]
// 
//
// 
//
// 限制： 
//
// 
// 0 <= matrix.length <= 100 
// 0 <= matrix[i].length <= 100 
// 
//
// 注意：本题与主站 54 题相同：https://leetcode-cn.com/problems/spiral-matrix/ 
// Related Topics 数组 矩阵 模拟 👍 291 👎 0


package leetcode.editor.cn1;

//Java：顺时针打印矩阵
public class ShunShiZhenDaYinJuZhenLcof {
    public static void main(String[] args) {
        Solution solution = new ShunShiZhenDaYinJuZhenLcof().new Solution();
        // TO TEST
        int[] order = solution.spiralOrder(new int[][]{
                {1,4,7},
                {2,5,8},
                {3,6,9},
                {10,11,12},
                {13,14,15}
        });
        for (int item : order) {
            System.out.print(item + ",");
        }
        System.out.println("");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] spiralOrder(int[][] matrix) {
            int rlen = matrix.length;
            if (rlen == 0)
                return new int[]{};
            int llen = matrix[0].length;
            int[] res = new int[rlen * llen];
            int reslen = res.length;
            // 0<=ri<=rlen
            // 0<=li<=llen
            // 右下左上
            recursive(res, 0, 0, 0, rlen, llen, matrix);
            return res;
        }

        public void recursive(int[] res, int k, int rstart, int lstart, int rlen, int llen, int[][] matrix) {
            if (rstart >= rlen || lstart >= llen)
                return;
            // 固定行不变，移动列
            for (int j = lstart; j < llen; j++) {
                res[k++] = matrix[rstart][j];
            }
            // 固定列不变，移动行
            for (int j = rstart + 1; j < rlen; j++) {
                res[k++] = matrix[j][llen - 1];
            }
            // 固定行不变，移动列
            if (rlen - 1 > rstart) {
                for (int j = llen - 2; j >= lstart; j--) {
                    res[k++] = matrix[rlen - 1][j];
                }
            }
            // 固定列不变，移动行
            if (llen - 1 > lstart) {
                for (int j = rlen - 2; j >= rstart + 1; j--) {
                    res[k++] = matrix[j][lstart];
                }
            }
            recursive(res, k, rstart + 1, lstart + 1, rlen - 1, llen - 1, matrix);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
